package sortArray;
/*
 * @lc app=leetcode.cn id=912 lang=java
 *
 * [912] 排序数组
 */

// @lc code=start
class Merge {
  int[] temp;

  public int[] sortArray(int[] nums) {
    int n = nums.length;
    temp = new int[n];
    merge(nums, 0, n - 1);
    return nums;
  }

  void merge(int[] nums, int l, int r) {
    if (l >= r) {
      return;
    }
    int mid = l + (r - l) / 2;
    merge(nums, l, mid);
    merge(nums, mid + 1, r);
    int i = l, j = mid + 1, idx = l;
    while (i <= mid && j <= r) {
      if (nums[i] < nums[j]) {
        temp[idx] = nums[i];
        i++;
      } else {
        temp[idx] = nums[j];
        j++;
      }
      idx++;
    }
    while (i <= mid) {
      temp[idx] = nums[i];
      i++;
      idx++;
    }
    while (j <= r) {
      temp[idx] = nums[j];
      j++;
      idx++;
    }
    for (int k = l; k <= r; k++) {
      nums[k] = temp[k];
    }
  }
}
// @lc code=end
